/*************************************************************************
*File Name: kmp.hpp
*Author: 侯广臣
*2801059691@qq.com
*Created Time: Mon 19 Apr 2021 05:56:30 PM CST
************************************************************************/
#ifndef _KMP_HPP_
#define _KEP_HPP_
#include <stdlib.h>
#include <string.h>
const size_t KMP_NOTFOUND = (size_t)-1; //表示没有找到

//初始化next数组，保存当前位置：前后缀最长相同长度
void KmpNext(char *str, size_t *next, size_t size)
{
    next[0] = 0;
    //i代表1、前缀子串末尾的下一个 2、当前位置前后子串最长相同长度
    //j为后缀子串末尾
    for(size_t i = 0, j = 1; j < size; ++j)
    {
        //如果当前最长相同前缀子串的下一个不等于后缀子串末尾则回退
        //直到上一个最长相同前缀子串的下一个等于后缀子串末尾，或者回退到最短相同前缀子串长度0
        while(i != 0 && str[i] != str[j])
        {
            i = next[i-1];
        }
        //如果当前位置最长相同前缀子串的下一个等于后缀子串的末尾
        //前进移动最长相同前缀子串末尾下标i，并更新当前位置最长相同前缀子串长度
        if(str[i] == str[j])
        {
            next[j] = ++i;
        }//其它情况则为最短相同前缀子串长度0
        else
        {
            next[j] = 0;
        }
    }
}

//在str1中寻找str2，返回首次匹配下标，没有找到返回KMP_NOTFOUND
size_t Kmp(char *str1, char *str2)
{
    if(str1 == NULL || str2 == NULL)
    {
        return KMP_NOTFOUND;
    }

    size_t size1 = strlen(str1);
    size_t size2 = strlen(str2);
    if(size2 > size1)
    {
        return KMP_NOTFOUND;
    }
    //初始化next数组，存储当前位置最长相同前缀子串长度
    //也是最长相同前缀子串下一个位置的下标
    size_t next[size2];
    KmpNext(str2, next, size2);

    size_t str1Index = 0, str2Index = 0;
    //开始比较，str1Index一直前进，str2Index只有两个字符串当前比较字符相同时前进
    for(str1Index = 0, str2Index = 0; str1Index < size1 && str2Index < size2;)
    {
        //如果当前比较字符相同，两个下标同时前进
        if(str1[str1Index] == str2[str2Index])
        {
            ++str1Index;
            ++str2Index;
        }//如果不同并且，str2Index不是0下标，回退str2Index
        else if(str2Index > 0)
        {
            str2Index = next[str2Index - 1];
        }//如果str2Index是0下标，前进str1Index
        else
        {
            ++str1Index;
        }
    }
    //如果str2全部比较完则说明有匹配项
    if(str2Index == size2)
    {
        return str1Index - str2Index;
    }
    return KMP_NOTFOUND;
}


#endif
